home *** CD-ROM | disk | FTP | other *** search
/ Aminet 1 (Walnut Creek) / Aminet - June 1993 [Walnut Creek].iso / aminet / util / gnu / textutl3.lha / textutils-1.3 / src / join.c < prev    next >
C/C++ Source or Header  |  1992-06-29  |  14KB  |  691 lines
  1. /* join - join lines of two files on a common field
  2.    Copyright (C) 1991 Free Software Foundation, Inc.
  3.  
  4.    This program is free software; you can redistribute it and/or modify
  5.    it under the terms of the GNU General Public License as published by
  6.    the Free Software Foundation; either version 2, or (at your option)
  7.    any later version.
  8.  
  9.    This program is distributed in the hope that it will be useful,
  10.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12.    GNU General Public License for more details.
  13.  
  14.    You should have received a copy of the GNU General Public License
  15.    along with this program; if not, write to the Free Software
  16.    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  17.  
  18.    Written by Mike Haertel, mike@gnu.ai.mit.edu. */
  19.  
  20. #define _GNU_SOURCE
  21. #include <ctype.h>
  22. #ifndef isblank
  23. #define isblank(c) ((c) == ' ' || (c) == '\t')
  24. #endif
  25. #include <stdio.h>
  26. #include <sys/types.h>
  27. #include <getopt.h>
  28. #include "system.h"
  29.  
  30. #ifdef isascii
  31. #define ISSPACE(c) (isascii(c) && isspace(c))
  32. #define ISDIGIT(c) (isascii(c) && isdigit(c))
  33. #else
  34. #define ISSPACE(c) isspace(c)
  35. #define ISDIGIT(c) isdigit(c)
  36. #endif
  37.  
  38. char *xmalloc ();
  39. char *xrealloc ();
  40. void error ();
  41. static void usage ();
  42.  
  43. #define min(A, B) ((A) < (B) ? (A) : (B))
  44.  
  45. /* An element of the list describing the format of each
  46.    output line. */
  47. struct outlist
  48. {
  49.   int file;            /* File to take field from (1 or 2). */
  50.   int field;            /* Field number to print. */
  51.   struct outlist *next;
  52. };
  53.  
  54. /* A field of a line. */
  55. struct field
  56. {
  57.   char *beg;            /* First character in field. */
  58.   char *lim;            /* Character after last character in field. */
  59. };
  60.  
  61. /* A line read from an input file.  Newlines are not stored. */
  62. struct line
  63. {
  64.   char *beg;            /* First character in line. */
  65.   char *lim;            /* Character after last character in line. */
  66.   int nfields;            /* Number of elements in `fields'. */
  67.   struct field *fields;
  68. };
  69.  
  70. /* One or more consecutive lines read from a file that all have the
  71.    same join field value. */
  72. struct seq
  73. {
  74.   int count;            /* Elements used in `lines'. */
  75.   int alloc;            /* Elements allocated in `lines'. */
  76.   struct line *lines;
  77. };
  78.  
  79. /* If nonzero, print unpairable lines in file 1 or 2. */
  80. static int print_unpairables_1, print_unpairables_2;
  81.  
  82. /* If nonzero, print pairable lines. */
  83. static int print_pairables;
  84.  
  85. /* Empty output field filler. */
  86. static char *empty_filler;
  87.  
  88. /* Field to join on. */
  89. static int join_field_1, join_field_2;
  90.  
  91. /* List of fields to print. */
  92. struct outlist *outlist;
  93.  
  94. /* Last element in `outlist', where a new element can be added. */
  95. struct outlist *outlist_end;
  96.  
  97. /* Tab character separating fields; if this is NUL fields are separated
  98.    by any nonempty string of white space, otherwise by exactly one
  99.    tab character. */
  100. static char tab;
  101.  
  102. /* The name this program was run with. */
  103. char *program_name;
  104.  
  105. /* Fill in the `fields' structure in LINE. */
  106.  
  107. static void
  108. xfields (line)
  109.      struct line *line;
  110. {
  111.   static int nfields = 2;
  112.   int i;
  113.   register char *ptr, *lim;
  114.  
  115.   line->fields = (struct field *) xmalloc (nfields * sizeof (struct field));
  116.  
  117.   ptr = line->beg;
  118.   lim = line->lim;
  119.  
  120.   for (i = 0; ptr < lim; ++i)
  121.     {
  122.       if (i == nfields)
  123.     {
  124.       nfields *= 2;
  125.       line->fields = (struct field *)
  126.         xrealloc ((char *) line->fields, nfields * sizeof (struct field));
  127.     }
  128.       if (tab)
  129.     {
  130.       line->fields[i].beg = ptr;
  131.       while (ptr < lim && *ptr != tab)
  132.         ++ptr;
  133.       line->fields[i].lim = ptr;
  134.       if (ptr < lim)
  135.         ++ptr;
  136.     }
  137.       else
  138.     {
  139.       line->fields[i].beg = ptr;
  140.       while (ptr < lim && !ISSPACE (*ptr))
  141.         ++ptr;
  142.       line->fields[i].lim = ptr;
  143.       while (ptr < lim && ISSPACE (*ptr))
  144.         ++ptr;
  145.     }
  146.     }
  147.  
  148.   line->nfields = i;
  149. }
  150.  
  151. /* Read a line from FP into LINE and split it into fields.
  152.    Return 0 if EOF, 1 otherwise. */
  153.  
  154. static int
  155. get_line (fp, line)
  156.      FILE *fp;
  157.      struct line *line;
  158. {
  159.   static int linesize = 80;
  160.   int c, i;
  161.   char *ptr;
  162.  
  163.   if (feof (fp))
  164.     return 0;
  165.  
  166.   ptr = xmalloc (linesize);
  167.  
  168.   for (i = 0; (c = getc (fp)) != EOF && c != '\n'; ++i)
  169.     {
  170.       if (i == linesize)
  171.     {
  172.       linesize *= 2;
  173.       ptr = xrealloc (ptr, linesize);
  174.     }
  175.       ptr[i] = c;
  176.     }
  177.  
  178.   if (c == EOF && i == 0)
  179.     {
  180.       free (ptr);
  181.       return 0;
  182.     }
  183.  
  184.   line->beg = ptr;
  185.   line->lim = line->beg + i;
  186.   xfields (line);
  187.   return 1;
  188. }
  189.  
  190. static void
  191. freeline (line)
  192.      struct line *line;
  193. {
  194.   free ((char *) line->fields);
  195.   free (line->beg);
  196. }
  197.  
  198. static void
  199. initseq (seq)
  200.      struct seq *seq;
  201. {
  202.   seq->count = 0;
  203.   seq->alloc = 1;
  204.   seq->lines = (struct line *) xmalloc (seq->alloc * sizeof (struct line));
  205. }
  206.  
  207. /* Read a line from FP and add it to SEQ.  Return 0 if EOF, 1 otherwise. */
  208.  
  209. static int
  210. getseq (fp, seq)
  211.      FILE *fp;
  212.      struct seq *seq;
  213. {
  214.   if (seq->count == seq->alloc)
  215.     {
  216.       seq->alloc *= 2;
  217.       seq->lines = (struct line *)
  218.     xrealloc ((char *) seq->lines, seq->alloc * sizeof (struct line));
  219.     }
  220.  
  221.   if (get_line (fp, &seq->lines[seq->count]))
  222.     {
  223.       ++seq->count;
  224.       return 1;
  225.     }
  226.   return 0;
  227. }
  228.  
  229. static void
  230. delseq (seq)
  231.      struct seq *seq;
  232. {
  233.   free ((char *) seq->lines);
  234. }
  235.  
  236. /* Return <0 if the join field in LINE1 compares less than the one in LINE2;
  237.    >0 if it compares greater; 0 if it compares equal. */
  238.  
  239. static int
  240. keycmp (line1, line2)
  241.      struct line *line1;
  242.      struct line *line2;
  243. {
  244.   char *beg1, *beg2;        /* Start of field to compare in each file. */
  245.   int len1, len2;        /* Length of fields to compare. */
  246.   int diff;
  247.  
  248.   if (join_field_1 < line1->nfields)
  249.     {
  250.       beg1 = line1->fields[join_field_1].beg;
  251.       len1 = line1->fields[join_field_1].lim
  252.     - line1->fields[join_field_1].beg;
  253.     }
  254.   else
  255.     {
  256.       beg1 = NULL;
  257.       len1 = 0;
  258.     }
  259.  
  260.   if (join_field_2 < line2->nfields)
  261.     {
  262.       beg2 = line2->fields[join_field_2].beg;
  263.       len2 = line2->fields[join_field_2].lim
  264.     - line2->fields[join_field_2].beg;
  265.     }
  266.   else
  267.     {
  268.       beg2 = NULL;
  269.       len2 = 0;
  270.     }
  271.  
  272.   if (len1 == 0)
  273.     return len2 == 0 ? 0 : -1;
  274.   if (len2 == 0)
  275.     return 1;
  276.   diff = memcmp (beg1, beg2, min (len1, len2));
  277.   if (diff)
  278.     return diff;
  279.   return len1 - len2;
  280. }
  281.  
  282. /* Print field N of LINE if it exists and is nonempty, otherwise
  283.    `empty_filler' if it is nonempty. */
  284.  
  285. static void
  286. prfield (n, line)
  287.      int n;
  288.      struct line *line;
  289. {
  290.   int len;
  291.  
  292.   if (n < line->nfields)
  293.     {
  294.       len = line->fields[n].lim - line->fields[n].beg;
  295.       if (len)
  296.     fwrite (line->fields[n].beg, 1, len, stdout);
  297.       else if (empty_filler)
  298.     fputs (empty_filler, stdout);
  299.     }
  300.   else if (empty_filler)
  301.     fputs (empty_filler, stdout);
  302. }
  303.  
  304. /* Print LINE, with its fields separated by `tab'. */
  305.  
  306. static void
  307. prline (line)
  308.      struct line *line;
  309. {
  310.   int i;
  311.  
  312.   for (i = 0; i < line->nfields; ++i)
  313.     {
  314.       prfield (i, line);
  315.       if (i == line->nfields - 1)
  316.     putchar ('\n');
  317.       else
  318.     putchar (tab ? tab : ' ');
  319.     }
  320. }
  321.  
  322. /* Print the join of LINE1 and LINE2. */
  323.  
  324. static void
  325. prjoin (line1, line2)
  326.      struct line *line1;
  327.      struct line *line2;
  328. {
  329.   if (outlist)
  330.     {
  331.       struct outlist *o;
  332.  
  333.       prfield (outlist->field - 1, outlist->file == 1 ? line1 : line2);
  334.       for (o = outlist->next; o; o = o->next)
  335.     {
  336.       putchar (tab ? tab : ' ');
  337.       prfield (o->field - 1, o->file == 1 ? line1 : line2);
  338.     }
  339.       putchar ('\n');
  340.     }
  341.   else
  342.     {
  343.       int i;
  344.  
  345.       prfield (join_field_1, line1);
  346.       for (i = 0; i < join_field_1 && i < line1->nfields; ++i)
  347.     {
  348.       putchar (tab ? tab : ' ');
  349.       prfield (i, line1);
  350.     }
  351.       for (i = join_field_1 + 1; i < line1->nfields; ++i)
  352.     {
  353.       putchar (tab ? tab : ' ');
  354.       prfield (i, line1);
  355.     }
  356.  
  357.       for (i = 0; i < join_field_2 && i < line2->nfields; ++i)
  358.     {
  359.       putchar (tab ? tab : ' ');
  360.       prfield (i, line2);
  361.     }
  362.       for (i = join_field_2 + 1; i < line2->nfields; ++i)
  363.     {
  364.       putchar (tab ? tab : ' ');
  365.       prfield (i, line2);
  366.     }
  367.       putchar ('\n');
  368.     }
  369. }
  370.  
  371. /* Print the join of the files in FP1 and FP2. */
  372.  
  373. static void
  374. join (fp1, fp2)
  375.      FILE *fp1;
  376.      FILE *fp2;
  377. {
  378.   struct seq seq1, seq2;
  379.   struct line line;
  380.   int diff, i, j, eof1, eof2;
  381.  
  382.   /* Read the first line of each file. */
  383.   initseq (&seq1);
  384.   getseq (fp1, &seq1);
  385.   initseq (&seq2);
  386.   getseq (fp2, &seq2);
  387.  
  388.   while (seq1.count && seq2.count)
  389.     {
  390.       diff = keycmp (&seq1.lines[0], &seq2.lines[0]);
  391.       if (diff < 0)
  392.     {
  393.       if (print_unpairables_1)
  394.         prline (&seq1.lines[0]);
  395.       freeline (&seq1.lines[0]);
  396.       seq1.count = 0;
  397.       getseq (fp1, &seq1);
  398.       continue;
  399.     }
  400.       if (diff > 0)
  401.     {
  402.       if (print_unpairables_2)
  403.         prline (&seq2.lines[0]);
  404.       freeline (&seq2.lines[0]);
  405.       seq2.count = 0;
  406.       getseq (fp2, &seq2);
  407.       continue;
  408.     }
  409.  
  410.       /* Keep reading lines from file1 as long as they continue to
  411.      match the current line from file2. */
  412.       eof1 = 0;
  413.       do
  414.     if (!getseq (fp1, &seq1))
  415.       {
  416.         eof1 = 1;
  417.         ++seq1.count;
  418.         break;
  419.       }
  420.       while (!keycmp (&seq1.lines[seq1.count - 1], &seq2.lines[0]));
  421.  
  422.       /* Keep reading lines from file2 as long as they continue to
  423.      match the current line from file1. */
  424.       eof2 = 0;
  425.       do
  426.     if (!getseq (fp2, &seq2))
  427.       {
  428.         eof2 = 1;
  429.         ++seq2.count;
  430.         break;
  431.       }
  432.       while (!keycmp (&seq1.lines[0], &seq2.lines[seq2.count - 1]));
  433.  
  434.       if (print_pairables)
  435.     {
  436.       for (i = 0; i < seq1.count - 1; ++i)
  437.         for (j = 0; j < seq2.count - 1; ++j)
  438.           prjoin (&seq1.lines[i], &seq2.lines[j]);
  439.     }
  440.  
  441.       for (i = 0; i < seq1.count - 1; ++i)
  442.     freeline (&seq1.lines[i]);
  443.       if (!eof1)
  444.     {
  445.       seq1.lines[0] = seq1.lines[seq1.count - 1];
  446.       seq1.count = 1;
  447.     }
  448.       else
  449.     seq1.count = 0;
  450.  
  451.       for (i = 0; i < seq2.count - 1; ++i)
  452.     freeline (&seq2.lines[i]);
  453.       if (!eof2)
  454.     {
  455.       seq2.lines[0] = seq2.lines[seq2.count - 1];
  456.       seq2.count = 1;
  457.     }
  458.       else
  459.     seq2.count = 0;
  460.     }
  461.  
  462.   if (print_unpairables_1 && seq1.count)
  463.     {
  464.       prline (&seq1.lines[0]);
  465.       freeline (&seq1.lines[0]);
  466.       while (get_line (fp1, &line))
  467.     {
  468.       prline (&line);
  469.       freeline (&line);
  470.     }
  471.     }
  472.  
  473.   if (print_unpairables_2 && seq2.count)
  474.     {
  475.       prline (&seq2.lines[0]);
  476.       freeline (&seq2.lines[0]);
  477.       while (get_line (fp2, &line))
  478.     {
  479.       prline (&line);
  480.       freeline (&line);
  481.     }
  482.     }
  483.  
  484.   delseq (&seq1);
  485.   delseq (&seq2);
  486. }
  487.  
  488. /* Add a field spec for field FIELD of file FILE to `outlist' and return 1,
  489.    unless either argument is invalid; then just return 0. */
  490.  
  491. static int
  492. add_field (file, field)
  493.      int file;
  494.      int field;
  495. {
  496.   struct outlist *o;
  497.  
  498.   if (file < 1 || file > 2 || field < 1)
  499.     return 0;
  500.   o = (struct outlist *) xmalloc (sizeof (struct outlist));
  501.   o->file = file;
  502.   o->field = field;
  503.   o->next = NULL;
  504.  
  505.   /* Add to the end of the list so the fields are in the right order. */
  506.   if (outlist == NULL)
  507.     outlist = o;
  508.   else
  509.     outlist_end->next = o;
  510.   outlist_end = o;
  511.  
  512.   return 1;
  513. }
  514.  
  515. /* Add the comma or blank separated field spec(s) in STR to `outlist'.
  516.    Return the number of fields added. */
  517.  
  518. static int
  519. add_field_list (str)
  520.      char *str;
  521. {
  522.   int added = 0;
  523.   int file = -1, field = -1;
  524.   int dot_found = 0;
  525.  
  526.   for (; *str; str++)
  527.     {
  528.       if (*str == ',' || isblank (*str))
  529.     {
  530.       added += add_field (file, field);
  531.       file = field = -1;
  532.       dot_found = 0;
  533.     }
  534.       else if (*str == '.')
  535.     dot_found = 1;
  536.       else if (ISDIGIT (*str))
  537.     {
  538.       if (!dot_found)
  539.         {
  540.           if (file == -1)
  541.         file = 0;
  542.           file = file * 10 + *str - '0';
  543.         }
  544.       else
  545.         {
  546.           if (field == -1)
  547.         field = 0;
  548.           field = field * 10 + *str - '0';
  549.         }
  550.     }
  551.       else
  552.     return 0;
  553.     }
  554.  
  555.   added += add_field (file, field);
  556.   return added;
  557. }
  558.  
  559. /* When using getopt_long_only, no long option can start with
  560.    a character that is a short option. */
  561. static struct option longopts[] =
  562. {
  563.   {"j", 1, NULL, 'j'},
  564.   {"j1", 1, NULL, '1'},
  565.   {"j2", 1, NULL, '2'},
  566.   {NULL, 0, NULL, 0}
  567. };
  568.  
  569. void
  570. main (argc, argv)
  571.      int argc;
  572.      char *argv[];
  573. {
  574.   char *names[2];
  575.   FILE *fp1, *fp2;
  576.   int optc, prev_optc = 0, nfiles, val;
  577.  
  578.   program_name = argv[0];
  579.   nfiles = 0;
  580.   print_pairables = 1;
  581.  
  582.   while ((optc = getopt_long_only (argc, argv, "-a:e:1:2:o:t:v:", longopts,
  583.                    (int *) 0)) != EOF)
  584.     {
  585.       switch (optc)
  586.     {
  587.     case 'a':
  588.       val = atoi (optarg);
  589.       if (val == 1)
  590.         print_unpairables_1 = 1;
  591.       else if (val == 2)
  592.         print_unpairables_2 = 1;
  593.       else
  594.         error (2, 0, "invalid file number for `-a'");
  595.       break;
  596.  
  597.     case 'e':
  598.       empty_filler = optarg;
  599.       break;
  600.  
  601.     case '1':
  602.       val = atoi (optarg);
  603.       if (val <= 0)
  604.         error (2, 0, "invalid field number for `-1'");
  605.       join_field_1 = val - 1;
  606.       break;
  607.  
  608.     case '2':
  609.       val = atoi (optarg);
  610.       if (val <= 0)
  611.         error (2, 0, "invalid field number for `-2'");
  612.       join_field_2 = val - 1;
  613.       break;
  614.  
  615.     case 'j':
  616.       val = atoi (optarg);
  617.       if (val <= 0)
  618.         error (2, 0, "invalid field number for `-j'");
  619.       join_field_1 = join_field_2 = val - 1;
  620.       break;
  621.  
  622.     case 'o':
  623.       if (add_field_list (optarg) == 0)
  624.         error (2, 0, "invalid field list for `-o'");
  625.       break;
  626.  
  627.     case 't':
  628.       tab = *optarg;
  629.       break;
  630.  
  631.     case 'v':
  632.       val = atoi (optarg);
  633.       if (val == 1)
  634.         print_unpairables_1 = 1;
  635.       else if (val == 2)
  636.         print_unpairables_2 = 1;
  637.       else
  638.         error (2, 0, "invalid file number for `-v'");
  639.       print_pairables = 0;
  640.       break;
  641.  
  642.     case 1:            /* Non-option argument. */
  643.       if (prev_optc == 'o')
  644.         {
  645.           /* Might be continuation of args to -o. */
  646.           if (add_field_list (optarg) > 0)
  647.         continue;    /* Don't change `prev_optc'. */
  648.         }
  649.  
  650.       if (nfiles > 1)
  651.         usage ();
  652.       names[nfiles++] = optarg;
  653.       break;
  654.  
  655.     case '?':
  656.       usage ();
  657.     }
  658.       prev_optc = optc;
  659.     }
  660.   
  661.   if (nfiles != 2)
  662.     usage ();
  663.  
  664.   fp1 = strcmp (names[0], "-") ? fopen (names[0], "r") : stdin;
  665.   if (!fp1)
  666.     error (1, errno, "%s", names[0]);
  667.   fp2 = strcmp (names[1], "-") ? fopen (names[1], "r") : stdin;
  668.   if (!fp2)
  669.     error (1, errno, "%s", names[1]);
  670.   if (fp1 == fp2)
  671.     error (1, errno, "both files cannot be standard input");
  672.   join (fp1, fp2);
  673.  
  674.   if ((fp1 == stdin || fp2 == stdin) && fclose (stdin) == EOF)
  675.     error (1, errno, "-");
  676.   if (ferror (stdout) || fclose (stdout) == EOF)
  677.     error (1, 0, "write error");
  678.  
  679.   exit (0);
  680. }
  681.  
  682. static void
  683. usage ()
  684. {
  685.   fprintf (stderr, "\
  686. Usage: %s [-a 1|2] [-v 1|2] [-e empty-string] [-o field-list...] [-t char]\n\
  687.        [-j[1|2] field] [-1 field] [-2 field] file1 file2\n",
  688.        program_name);
  689.   exit (1);
  690. }
  691.